package practice;

import java.util.Scanner;

public class Day15 {
    //背包问题（经典动态规划）
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        int V = in.nextInt();
        int[] v = new int[n];
        int[] w = new int[n];
        for(int i = 0; i < n; i++) {
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        int max1 = 0;
        int max2 = 0;
        //从前i个位置挑选总体积不超过j，所有选法中能挑选出来地最大价值
        int[][] dp1 = new int[n+1][V+1];
        //从前i个位置挑选总体积等于j，所有选法中能挑选出来地最大价值
        int[][] dp2 = new int[n+1][V+1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= V; j++) {
                dp1[i][j] = dp1[i-1][j];
                if(j - v[i-1] >= 0) {
                    dp1[i][j] = Math.max(dp1[i-1][j],w[i-1]+dp1[i-1][j-v[i-1]]);
                }
                max1 = Math.max(dp1[i][j],max1);
            }
        }
        for(int i = 1; i <= V; i++) {
            dp2[0][i] = -1;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= V; j++) {
                dp2[i][j] = dp2[i-1][j];
                if(j - v[i-1] >= 0 && dp2[i-1][j-v[i-1]] != -1) {
                    dp2[i][j] = Math.max(dp2[i-1][j],w[i-1]+dp2[i-1][j-v[i-1]]);
                }
                max2 = Math.max(dp2[i][V],max2);
            }
        }
        System.out.println(max1);
        System.out.println(max2);
    }
}
